// 文件名：exercise\lc94_姓名(演示).cpp
// 提交链接：https://www.lanqiao.cn/problems/4861/learning/
// 坤坤的魔法游戏 - 数学题，找规律+素数+前缀和知识
// 完成日期：2024/9/6
/*
通过找规律可得：
在2~N中，2~(N/2)的数乘以2其实都能在4~N都找到,
而N/2~N除了素数以外的数，都能与前面的某一个数有共同因子，所以它们将组成一个组(因为等价关系)
所以...
    2~N/2与N/2~N的非素数将成为一组
    N/2~N中的素数各自成为一组
    坤坤的任务：是找出最后形成的组的总数(sum)。
    关键就是求N/2~N之间到底有多少个素数?
    所以可以通过埃氏筛法先把素数筛出来，然后再利用前缀和去相减
    更多详细见：https://blog.csdn.net/2301_79370590/article/details/139105601?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522171631249116800184170733%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=171631249116800184170733&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-139105601-null-null.142%5Ev100%5Epc_search_result_base1&utm_term=%E5%9D%A4%E5%9D%A4%E7%9A%84%E9%AD%94%E6%B3%95%E6%B8%B8%E6%88%8F&spm=1018.2226.3001.4187
*/

#include <iostream>
using namespace std;
const int MAX=10000001; 
int fac[MAX]={0},a[MAX]={0},num=0;   //num记录有多少个素数
void ai(){//埃氏筛法
  for(int i=2;i<MAX;++i){
  if(fac[i]==0)
    for(int j=i;j<MAX;j+=i)
    fac[j]=i;
  if(fac[i]==i) ++num;    //如果(fac[i]==i),则说明i是素数,更新num
  a[i]=num;  //a[i]存储从2到i之间有多少个素数
  }       //a[2]=1,a[3]=2,a[4]=2,a[5]=3,a[6]=3,a[7]=4
}

int main()
{
  ai();
  int T,N,sum;  //sum为总组数
  cin>>T;
  while(T--){
    cin>>N;
    sum=1;   //2~N/2的数和N/2~N的非素数为一组
    //if(N/2<2) --sum;  N==2||N==3的情况sum会多算一次 ,虽然测试用例没有
    sum+=a[N]-a[N/2];  
    cout<<sum<<endl;
    }
  return 0;
}